package cxydmmszl.chapter02.t016;

/**
 * <li style="color: red;">Prob</li>
 * 反转部分单链表
 * <li style="color: red;">Desc</li>
 * 给定一个单链表的头节点 head，以及两个整数 from 和 to，在单向链表上把第 from 个节点到第 to 个节点这一部分进行反转。<br/>
 * 例如：<br/>
 * &emsp;1->2->3->4->5->null, from=2, to=4<br/>
 * &emsp;调整结果为：1->4->3->2->5->null<br/>
 * <li style="color: red;">Link</li> CD108
 *
 * @author habitplus
 * @since 2021-08-28 12:52
 */
public class Main {
    private static class Node {
        int val;
        Node next;

        public Node(int val) {
            this.val = val;
        }
    }

    public Node reverseLinkedList(Node head) {
        Node pre = null;
        Node t;
        while (head != null) {
            t = head.next;
            head.next = pre;
            pre = head;
            head = t;
        }
        return pre;
    }

    public Node reversePartLinkedList(Node head, int from, int to) {
        if (head == null || from < 1 || from >= to) {
            return head;
        }

        // 1. 将链表在第 to 个节点处断开，得到 midTail 和 rightHead
        // 2. 将链表遍历在第 from 个节点处断开，得到 leftTail 和 midHead
        // 3. 将上述得到的从 from 至 to 段子链表反转
        Node midTail = head;
        while (--to > 0 && midTail != null) {
            midTail = midTail.next;
        }

        // to 越界了
        if (midTail == null) { return head; }

        // 断开 to 处的链表
        Node rightHead = midTail.next;
        midTail.next = null;


        Node leftTail = null;
        Node midHead = head;
        while (--from > 0) {
            leftTail = midHead;
            midHead = midHead.next;
        }


        // 反转 form 到 to 段子链表
        midTail = reverseLinkedList(midHead);


        if (leftTail != null) {
            leftTail.next = midTail;
        } else {
            // 反转至第一个节点，即 from=1
            head = midTail;
        }
        midHead.next = rightHead;

        return head;
    }
}
